#include "linearList.h"
#include <iostream> 
//顺序表打印
void sequenceList::print()
{
    cout << curNumberOfItem << ":";

    for(int i = 0; i < curNumberOfItem-1; i++)
    {
        cout << myList[i] << ",";
    }

    cout << myList[curNumberOfItem-1] << endl;
}



//链表打印
void linkList::print()
{
    curNode = firstNode;

    cout << listSize << ":";

    while(curNode != lastNode)
    {
        if(curNode->next == lastNode)
            cout << curNode->next->data << endl;
        else
        {
            cout << curNode->next->data << ",";
        }
        
        
        curNode = curNode->next;
    }
}

//顺序表任务
sequenceList::sequenceList(const int& max, const int& item, float list[]) {
        maxCapcity = max;
        if(maxCapcity > 0) {
            myList = new float[maxCapcity];
        } else {
            myList = nullptr;
            maxCapcity = 0;
            cout << "maxCapacity is illegal";
        }

        if(item > maxCapcity) {
            curNumberOfItem = maxCapcity;
        } else if(item < 0) {
            curNumberOfItem = 0;
        } else {
            curNumberOfItem = item;
        }

        if(myList != nullptr) {
            for(int i = 0; i < curNumberOfItem; i ++) {
                myList[i] = list[i];
            }
        } else {
            cout << "MyList falis to create.";
        }
    };

sequenceList::~sequenceList() {
    delete myList;
    myList = nullptr;
}

bool sequenceList::addItem(const float &addition){
    if(curNumberOfItem < maxCapcity) {
        myList[curNumberOfItem] = addition;
        curNumberOfItem ++;
        return true;
    }
    return false;
}

bool sequenceList:: insertItem(const int &location, const float &insertion) {
    if(curNumberOfItem < maxCapcity) {
        if(location < curNumberOfItem) {
            for(int i = curNumberOfItem; i > location; i --) {
                myList[i] = myList[i - 1];
            }
            myList[location] = insertion;
            curNumberOfItem ++;
            return true;
        } else if(location == curNumberOfItem) {
            myList[location] = insertion;
            curNumberOfItem ++;
            return true;
        }
    }
    return false;
}

int sequenceList::deleteItem(const float &delete_num) {
    int delete_loc = -1;
    if(curNumberOfItem > 0) {
        for(int i = 0; i < curNumberOfItem; i ++){
            if(myList[i] == delete_num) {
                delete_loc = i;
                break;
            }
        }
        if(delete_loc != -1) {
            for(int i = delete_loc; i < curNumberOfItem - 1; i ++) {
                myList[i] = myList[i + 1];
            }
        }
    }
    if(delete_loc != -1) {
        curNumberOfItem --;
    }
    return delete_loc;
}

bool sequenceList::locate(const int &location, float &val){
    if(location >= 0 && location < curNumberOfItem) {
        val = myList[location];
        return true;
    }
    return false;
}

int sequenceList::locate(const float &locate_num_2) {
    int location = -1;
    for(int i = 0; i < curNumberOfItem; i ++) {
        if(myList[i] == locate_num_2) {
            location = i;
            break;
        }
    }
    return location;
}

void sequenceList::reverse() {
    int start = 0;
    int end = curNumberOfItem - 1;

    while (start < end) {
        float temp = myList[start];
        myList[start] = myList[end];
        myList[end] = temp;

        start++;
        end--;
    }
}

//顺序表结束

//节点任务
listNode::listNode(float data_num, listNode *success) {
    data = data_num;
    next = success;
}

listNode::~listNode() {
    next = nullptr;
}

//链表任务
linkList::linkList(const int& size,float nums[]){
    listSize = size;
    firstNode = new listNode();
    
    curNode = new listNode();
    firstNode->next = curNode;
    
    for(int i = 0; i < size - 1;i ++){
        
        curNode->data = nums[i];
        curNode->next = new listNode();
        curNode = curNode->next;
    }
    curNode->data = nums[size-1];
    lastNode = curNode;
}

linkList::~linkList() {
    listNode *curr = firstNode;
    listNode *next = nullptr;
    while (curr != nullptr) {
        next = curr->next;
        delete curr;
        curr = next;
    }
    firstNode = nullptr;
    lastNode = nullptr;
}

bool linkList::headInsertItem(const float &insertion_head) {
    listNode *newhead = new listNode(insertion_head);
    if(newhead == nullptr) {
        return false;
    }
    newhead->next = firstNode->next;
    firstNode->next = newhead;
    listSize++;
    return true;
}

bool linkList::tailInsertItem(const float &insertion_tail) {
    listNode *tmp = new listNode(insertion_tail);
    if(tmp == nullptr) {
        return false;
    }
    
    tmp->next = nullptr;
    
    lastNode->next = tmp;
    lastNode = tmp;
    listSize ++;
    return true;
}

int linkList::insertItem(const int &insert_loc,const float &insert_num) {
    if (insert_loc < 0 || insert_loc > listSize) {
        return -1;
    }
    if (insert_loc == 0) {
        headInsertItem(insert_num);
        return 0;
    }
    if (insert_loc == listSize) {
        tailInsertItem(insert_num);
        return insert_loc;
    }
    curNode = firstNode;
    for(int i = 0; i < insert_loc; i ++) {
        curNode = curNode->next;
    }
    listNode *ins = new listNode(insert_num, curNode->next);
    curNode->next = ins;
    listSize++;
    return insert_loc;
}

int linkList::deleteItem(const float &delete_num) {
    listNode *prev = firstNode; 
    listNode *curr = firstNode->next;
    int num = 0; 
    
    while (curr != nullptr) {
        if (curr->data == delete_num) {
            prev->next = curr->next; 
            
            if (curr == lastNode) {
                lastNode = prev;
            }
            
            delete curr;
            listSize--;
            return num;
        }
        prev = curr;
        curr = curr->next;
        num++;
    }
    return -1;
}

bool linkList::locate(const int &locate_num, float &val) {
    if(locate_num < 0 || locate_num >= listSize) {
        return false;
    }
    listNode *curr = firstNode->next;
    for(int i = 0; i < locate_num; i ++, curr = curr->next) {
        
    }
    val = curr->data;
    return true;
}

int linkList::locate(const float &locate_num) {
    listNode *curr = firstNode;
    int num = -1, i = -1;
    for(; curr != nullptr; curr = curr->next, i ++) {
        if(curr->data == locate_num) {
            num = i;
            break;
        }
    }
    return num; 
}

void linkList::ascendingOrder() {
    float *arr = new float[listSize];
    listNode *curr = firstNode->next;
    int i = 0;

    for(; curr != nullptr; curr = curr->next, i ++) {
        arr[i] = curr->data;
    }

    for(int j = 1; j < listSize; j ++) {
        float key = arr[j];
        int k = j - 1;
        while(k >= 0 && arr[k] > key) {
            arr[k + 1] = arr[k];
            k --;
        }
        arr[k + 1] = key;
    }
    curr = firstNode->next;
    for(int i = 0; i < listSize; i ++, curr = curr->next) {
        if(curr != nullptr) {
            curr->data = arr[i];
        }
    }
    delete[] arr;
}

void linkList::reverse() {
    if (firstNode == nullptr || firstNode->next == nullptr) {
        return;
    }
        
    listNode *prev = nullptr;
    listNode *curr = firstNode->next; 
    listNode *next;
        
    listNode *new_tail = curr; 
        
    while(curr != nullptr) {
        next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
        
    listNode *new_head = prev; 
        
    firstNode->next = new_head;
    lastNode = new_tail;
    /*listNode *prev = firstNode->next;
    float *arr = new float [listSize];
    int i = 0;
    for(; prev != nullptr; prev = prev->next, i ++) {
        arr[i] = prev->data;
    }
    prev = firstNode->next;
    for(int i = listSize - 1; i >= 0; i --, prev = prev->next) {
        prev->data = arr[i];
    }*/

    
}


void merge(linkList &list1, linkList &list2) {
    listNode *dummy = new listNode(); 
    listNode *head = dummy; 
    
    listNode *curr1 = list1.firstNode->next;
    listNode *curr2 = list2.firstNode->next;

    while (curr1 != nullptr && curr2 != nullptr) {
        if (curr1->data <= curr2->data) {
            head->next = curr1; 
            curr1 = curr1->next;
        } else {
            head->next = curr2; 
            curr2 = curr2->next;
        }
        head = head->next; 
    }

    if (curr1 != nullptr) {
        head->next = curr1;
    } else {
        head->next = curr2;
    }
    
    list1.listSize += list2.listSize;
    
    list1.firstNode->next = dummy->next;
    
    while (head->next != nullptr) {
        head = head->next;
    }
    list1.lastNode = head;
    
    list2.firstNode->next = nullptr;
    list2.lastNode = list2.firstNode; 
    list2.listSize = 0;

    list1.reverse();
    delete dummy;
}






